import copy


class Solution(object):
    def slidingPuzzle(self, board):
        def convert_tuple(state):
            return (tuple(state[0]), tuple(state[1]))

        start = convert_tuple(board)
        end = convert_tuple([[1, 2, 3], [4, 5, 0]])
        k = 0
        start_set = {start}
        end_set = {end}
        already_set = {start, end}
        if start == end:
            return k

        def find_next(state):
            state = [list(state[0]), list(state[1])]
            for i in range(2):
                for j in range(3):
                    if state[i][j] == 0:
                        x, y = i, j
                        break
            out = set()
            for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= ux < 2 and 0 <= uy < 3:
                    next_state = copy.deepcopy(state)
                    next_state[x][y], next_state[ux][uy] = next_state[ux][uy], next_state[x][y]
                    out.add(convert_tuple(next_state))
            return out

        while start_set and end_set:
            k += 1
            next_st = set()
            if k % 2:
                for state in start_set:
                    next_state = find_next(state)
                    for s in next_state:
                        if s in end_set:
                            return k
                        if s not in already_set:
                            already_set.add(s)
                            next_st.add(s)
                start_set = next_st
            else:
                for state in end_set:
                    next_state = find_next(state)
                    for s in next_state:
                        if s in start_set:
                            return k
                        if s not in already_set:
                            already_set.add(s)
                            next_st.add(s)
                end_set = next_st

        return -1


data = Solution()
board = [[1,2,3],[4,0,5]]
print(data.slidingPuzzle(board))
